/************************************************************************

								Heroes IV
					  Copyright 2000, The 3DO Company

	------------------------------------------------------------------
  						       clip_list.h

	$Header: /game/clip_list.h $

	$NoKeywords: $

 ************************************************************************/

#ifndef SORTED_CLIP_LIST_H_INCLUDED
#define SORTED_CLIP_LIST_H_INCLUDED

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

#include <algorithm>
#include <list>
#include <map>
#include <vector>

#include "clip_list.h"
#include "screen_point.h"


typedef std::list<t_screen_rect>::iterator					t_rect_iterator;
typedef std::list<t_rect_iterator>							t_rect_iterator_list;

struct t_quadtree_node
{
	/////////////////////////////////////////
	//		a  |  b 
	//		-------
	//		c  |  d
	////////////////////////////////////////

	t_screen_rect		area;

	short	node_a;
	short	node_b;
	short	node_c;
	short	node_d;

	t_rect_iterator_list	rect_iterator_list;
};


// ---------------------------------------------------------------
// object to maintain a list of valid rectangles for drawing
// ---------------------------------------------------------------
class t_sorted_clip_list 
{
public:

	typedef std::list<t_screen_rect>	t_rect_list;
	
	t_sorted_clip_list();
	t_sorted_clip_list( int sub_division_level, t_screen_rect extent );
	~t_sorted_clip_list();

	void 			clear( t_screen_rect const & new_area );
	void 			insert( t_screen_rect const & insert_rect, bool split );
	void			insert( t_screen_rect_list const & insert_rect_list, bool split );
	void 			intersect( t_screen_rect const & query_area , t_rect_list & result );
	void 			intersect( t_screen_rect const & query_area );
	void 			offset( t_screen_point const & offset );
	bool			preallocate_quadtree_nodes( t_screen_rect extent );
	bool 			preallocate_quadtree_nodes( int sub_division_level, t_screen_rect extent );
	void 			remove( t_screen_rect const & remove_rect );
	void 			verify_tree();
	
protected:
	
	void 				add_rect( t_quadtree_node & quad_node, t_screen_rect & insert_rect );
	bool 				assign_nodes( t_quadtree_node* parent_node, int & current_index, int current_level);
	bool				calcuate_quadtree_child_area(	
								t_screen_rect & area_a,
								t_screen_rect & area_b,
								t_screen_rect & area_c,
								t_screen_rect & area_d,
								t_screen_rect & area_parent);
	void				check_m_rects();
	void				fill_list_with_all_rects( t_rect_list & fill_list );
	t_quadtree_node*	find_insert_node( t_quadtree_node & parent_node, t_screen_rect & insert_rect, int depth );

	void				insert_rect_into_tree( t_quadtree_node & parent_node, t_screen_rect & insert_rect, t_rect_list & split_list, int depth, bool & can_insert_rect );
	void				insert_rect( t_quadtree_node & quad_node, t_screen_rect & insert_rect, t_rect_list & split_list, bool & can_insert_rect );

	void				intersect( t_quadtree_node& parent_node, t_screen_rect const & query_area , t_rect_list & result, int depth );
	void 				intersect_rect( t_quadtree_node & quad_node, t_screen_rect const & insert_rect, t_rect_list & split_list );

	void				merge_rects_with( t_screen_rect & query_rect, t_rect_list & merge_list );
	void 				resort_all();

	void 				split_rect( t_quadtree_node & quad_node, t_screen_rect & insert_rect, t_rect_list & split_list );
	bool 				split_rect( t_screen_rect  & major_rect, t_screen_rect & minor_rect, t_rect_list & split_list );
	void 				split_tree_against_rect( t_quadtree_node & parent_node, t_screen_rect & insert_rect, t_rect_list & split_list, int depth );

	void 				remove_rect_from_tree( t_quadtree_node& parent_node, t_screen_rect const & query_area );
	void 				update_extent();
	
	t_screen_rect								m_extent;
	t_rect_list_cache_ptr						m_global_free_rect_list;
	t_uint32									m_intersect_threshold;
	t_uint32									m_insert_threshold;
	t_quadtree_node								m_parent_node;
	std::vector<t_quadtree_node>				m_quadtree_array;
	int											m_quadtree_array_size;
	t_rect_list									m_rects;
	t_uint32									m_remove_threshold;
	t_rect_list									m_split_list;
	int											m_sub_division_level;

};


#endif // SORTED_CLIP_LIST_H_INCLUDED